/**
 * Algorithm.java 
 * @author Matan Ginzburg 203827753
 *
 */

import java.util.*;


public class Algorithm {

	public static HashSet<Integer> SFT(Function f, double tau, double delta, double norm){
		
		/**Define constant**/
		double A = 10;
		/**Return to function**/
		
		double norm2 = est2Norm(f);
		int n = f.getN();
		HashMap<Integer, Complex> Q = new HashMap<Integer, Complex>();
		HashSet<Integer>[] AB;
		HashSet<Integer> B;
		
		AB = generateQueries(n, tau/36, norm, A*delta/(log2(n)*Math.pow(norm2/tau, 1.5)));
		B = new HashSet<Integer>();
		
		for(int i = 1; i<AB.length; i++) 
			B.addAll(AB[i]);
		
		for(int a : AB[0]){
			for(int b : B)
				Q.put(a-b, f.apply(a-b));
		}
		return fixedQuriesSFT(n, tau, AB, Q);

	}
	
	private static HashSet<Integer> fixedQuriesSFT(int n, double tau, HashSet<Integer>[] AB, HashMap<Integer, Complex> Q) {
		HashSet<HashSet<Integer>> current, next;
		HashSet<Integer> ret;
		HashSet<Integer> temp;
		
		current = new HashSet<HashSet<Integer>>();
		temp = new HashSet<Integer>();
		temp.add(0);
		temp.add(n-1);
		current.add(temp);
		
		for(int l = 0; l<log2(n); l++) {
			next = new HashSet<HashSet<Integer>>();
			for (HashSet<Integer> ab: current) {
				int a = getMin(ab), b = getMax(ab);
				if(Distinguish(n, a, (a+b)/2, tau, AB[0], AB[l+1], Q)) {
					temp = new HashSet<Integer>();
					temp.add(a);
					temp.add((a+b)/2);
					next.add(temp);
				}
				if(Distinguish(n, ((a+b)/2)+1, b, tau, AB[0], AB[l+1], Q)) {
					temp = new HashSet<Integer>();
					temp.add((a+b)/2+1);
					temp.add(b);
					next.add(temp);
				}
			}
			current = next;
		}
		ret = new HashSet<Integer>();
		for(HashSet<Integer> s: current)
			if(s.size()==1 && Distinguish(n, getMin(s), getMin(s), tau, AB[0], AB[AB.length-1], Q))
				ret.add(getMin(s));
		return ret;
	}
	
	private static HashSet<Integer>[] generateQueries(int n, double gamma, double norm, double delta) {

		/**Define constants**/
		double A = 0.00002;
		double B = 0.0002;
		double C = 1;
		/**Return to function**/
		
		HashSet<Integer>[] ret = new HashSet[1+log2(n)+1];
		double eta = C*Math.min(gamma, Math.min(Math.sqrt(gamma), gamma/norm));
		int mA = (int) (A*Math.pow(norm/eta, 2)*Math.log(1/delta)/Math.log(2));
		int mB = (int) (B*Math.pow(norm/eta, 2)*Math.log(norm/(delta*gamma))/Math.log(2));
		
		mA = Math.min(mA, n);
		
		ret[0] = getRandomSubset(n, mA);
		
		for (int i = 1; i < ret.length-1; i++)
			ret[i] = getRandomSubset((int) Math.pow(2, i-1), (int) Math.min(mB, Math.pow(2, i-1)));
		ret[ret.length-1] = getRandomSubset(n,  (int) Math.min(Math.min(mB, Math.pow(2, log2(n))), n));
		
		return ret;
	}
	
	
	private static boolean Distinguish(int n, double a, double b, double tau, HashSet<Integer> A, HashSet<Integer> B,
										HashMap<Integer, Complex> Q){
		double est = 0;
		
		for (int x : A) {
			Complex temp = new Complex();
			for (int y : B)
				temp.Add(Complex.Mult(Complex.Chi((a+b)/2, y, n), Q.get(x-y)));
			
			est += Math.pow(Complex.Abs(temp)/B.size(),2);
		}
		est = est/A.size();
		
		return est>=5*tau/36;
	}
	
	private static int log2(int n){
		return (int) (Math.log(n)/Math.log(2));
	}
	
	private static double est2Norm(Function f) {
		int size = Math.min(10, f.getN());
		HashSet<Integer> sample = getRandomSubset(f.getN(), size);
		double ret = 0;
	
		for (Integer x : sample)
			ret += Math.pow(Complex.Abs(f.apply(x)),2);
		
		return ret/(size*size);
	}
	
	private static HashSet<Integer> getRandomSubset(int N, int size) {
		HashSet<Integer> ret = new HashSet<Integer>();
		
		for(int i = 0; i<size; i++) {
			int rand = (int) Math.round((N-1)*Math.random());
			while(ret.contains(rand))
				rand = (int) Math.round((N-1)*Math.random());
			ret.add(rand);
		}
		
		return ret;
	}
	
	private static int getMin(HashSet<Integer> ab){
		Iterator<Integer> iter = ab.iterator();
		int a,b;
		
		a = iter.next();
		if(!iter.hasNext())
			return a;
		b = iter.next();
		
		if(b<a)
			return b;
		return a;
	}
	
	private static int getMax(HashSet<Integer> ab){
		Iterator<Integer> iter = ab.iterator();
		int a,b;
		
		a = iter.next();
		if(!iter.hasNext())
			return a;
		b = iter.next();
		
		if(b>a)
			return b;
		return a;
	}
}
